This disclosure relates generally to techniques for generating valid polygon data for graphical display on a display screen of a computing device, particularly where input data used to generate the polygons includes errors.
Electronic maps are becoming increasingly used to represent spatial aspects of a given geographic area. These maps are often comprised of polygons arranged within a coordinate system to provide a user with an accurate representation of buildings, major road arteries, or other points of interest. Polygons may be used to represent objects, for example physical locations within an electronic map. In order to generate polygons for display, polygon Boolean operation algorithms, such as the Vatti algorithm, can be implemented to improve the quality of polygon data representing areas within the electronic map. In particular, polygon Boolean operation algorithms can improve the quality of polygon data where polygons overlap. Polygon Boolean operation algorithms (e.g., polygon clipping algorithms) often operate on a first polygon, or “subject polygon,” using a second polygon, or “operating polygon,” to perform various Boolean operation types (e.g., intersection, union, difference, and exclusive-or). However, existing polygon Boolean operation algorithms do not account for numerous edge cases associated with polygon Boolean operations. For example, polygons that intersect themselves (e.g., self-intersecting polygons), polygons that intersect each other, polygons that include one or more intersecting interior polygons, or “holes,” (e.g., chain of holes), and/or polygons that include complex intersections are often ambiguously processed by polygon Boolean operation algorithms to produce invalid polygons.